package day_2022_4_to_7.nowcoder;

/**
 * 连续子数组的最大和
 * @author haomin
 * @date 2022/05/05 21:06
 **/
public class FindGreatestSumOfSubArray_25f {
    public static void main(String[] args) {
        FindGreatestSumOfSubArray(new int[]{1,-2,3,10,-4,7,2,-5});
    }

    // 方法一 动态规划
    public static int FindGreatestSumOfSubArray1(int[] array) {
        int[] dp = new int[array.length];
        // 初始化
        int maxSum = array[0];
        dp[0] = array[0];
        // 遍历
        for (int i = 1; i < dp.length; i++) {
            // dp[i] 中一直存储的是((dp[i-1]+array[i]) 和 array[i]) 中的较大值
            dp[i] = Math.max(dp[i-1]+array[i],array[i]);
            // 更新最大值
            maxSum = Math.max(maxSum,dp[i]);
        }
        return maxSum;
    }

    // 方法二
    public static int FindGreatestSumOfSubArray(int[] array) {
        // 初始化
        int maxSum = array[0];
        int sum = array[0];
        // 遍历
        for (int i = 1; i < array.length; i++) {
            if(sum < 0){
                // 当sum < 0 时，更新sum
                sum = array[i];
            }else {
                // 当sum > 0 时，继续sum+=array[i]
                sum += array[i];
            }
            // maxSum一直存储sum的最大值
            maxSum = Math.max(maxSum,sum);
        }
        return maxSum;
    }
}